package 图.树.树形DP;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/15 11:42
 */
public class lc110平衡二叉树 {

    /*
     典型的 树形dp
     */
    public int[] recursion(TreeNode node){
           if(node == null){
               return new int[]{0,0}; // 当前节点 子树的 高度, 以及当前节点是 否为 平衡二叉树, 0 是 1 不是
           }
           int left[] = recursion(node.left);
           int right[] = recursion(node.right);
           if(left[1] == 1 || right [1] == 1 || Math.abs(left[0] - right[0]) > 1){
               return new int[]{0,1}; // 直接 返回 不是 平衡二叉树
           }
           return new int[]{Math.max(left[0],right[0]) + 1  ,0};
    }
    public boolean  solve(TreeNode root){
        return recursion(root)[1] == 0;
    }

    class TreeNode{
        int val;
       TreeNode left;
       TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }

    }

}
